KOrderedLCS.java

packagesection19_DynamicProgramming;

importjava.util.Arrays;

publicclassKOrderedLCS {

publicstaticvoidmain(String[] args) {

Strings1 = "abcd", s2 = "agcfde"; // 4
// String s1 = "abc", s2 = "abcd";
// String s1 = "abchd", s2 = "agcfd";
// String s1 = "qwerqwrf", s2 = "aehfdaz";
// String s1 = "abcd", s2 = "brdce";
// String s1 = "sufdnsdgpa", s2="qiwohdfgefqa";

// String s1 = "aqieowf lasansd candv qpoizion'";
// String s2 = "soehgpwz pqoiw qomashfklvifa";

intK = 2; // can change at most k character to make subsequences

System.out.println(kOrderedLCSRecursion(s1, s2, K, 0, 0));

int[][][] storage = newint[K + 1][s1.length()][s2.length()];
for (inti = 0; i < storage.length; i++) {
for (intj = 0; j < storage[0].length; j++) {
Arrays.fill(storage[i][j], -1);
 }
 }
// display(storage);
System.out.println(kOrderedLCSTopDownDP(s1, s2, K, 0, 0, storage));

System.out.println(kOrderedLCSBottomUpDP(s1, s2, K));
 }

publicstaticintkOrderedLCSRecursion(Strings1, Strings2, intk, intvidx1, intvidx2) {

if (vidx1 == s1.length() || vidx2 == s2.length())
return0;

charch1 = s1.charAt(vidx1);
charch2 = s2.charAt(vidx2);

intlcsLen = 0;
if (ch1 == ch2) {
lcsLen = 1 + kOrderedLCSRecursion(s1, s2, k, vidx1 + 1, vidx2 + 1);
 } else {
intfactor1 = kOrderedLCSRecursion(s1, s2, k, vidx1, vidx2 + 1);
intfactor2 = kOrderedLCSRecursion(s1, s2, k, vidx1 + 1, vidx2);

intfactor3 = 0;
if (k >= 1)
factor3 = 1 + kOrderedLCSRecursion(s1, s2, k - 1, vidx1 + 1, vidx2 + 1);

lcsLen = Math.max(factor1, Math.max(factor2, factor3));
 }

returnlcsLen;
 }

publicstaticintkOrderedLCSTopDownDP(Strings1, Strings2, intk, intvidx1, intvidx2, int[][][] storage) {

if (vidx1 == s1.length() || vidx2 == s2.length())
return0;

if (storage[k][vidx1][vidx2] != -1) {
returnstorage[k][vidx1][vidx2];
 }

charch1 = s1.charAt(vidx1);
charch2 = s2.charAt(vidx2);

intlcsLen = 0;
if (ch1 == ch2) {
lcsLen = 1 + kOrderedLCSTopDownDP(s1, s2, k, vidx1 + 1, vidx2 + 1, storage);
 } else {
intfactor1 = kOrderedLCSTopDownDP(s1, s2, k, vidx1, vidx2 + 1, storage);
intfactor2 = kOrderedLCSTopDownDP(s1, s2, k, vidx1 + 1, vidx2, storage);

intfactor3 = 0;
if (k >= 1)
factor3 = 1 + kOrderedLCSTopDownDP(s1, s2, k - 1, vidx1 + 1, vidx2 + 1, storage);

lcsLen = Math.max(factor1, Math.max(factor2, factor3));
 }
storage[k][vidx1][vidx2] = lcsLen;

returnlcsLen;
 }

publicstaticintkOrderedLCSBottomUpDP(Strings1, Strings2, intK) {

int[][][] storage = newint[K + 1][s1.length() + 1][s2.length() + 1];

for (intkth = 0; kth <= K; kth++) {

// -2, as by default last row will also be initialized with zero
for (introw = storage[kth].length - 2; row >= 0; row--) {

for (intcol = storage[kth][row].length - 2; col >= 0; col--) {

// logic from top down
intlcsLen = 0;

if (s1.charAt(row) == s2.charAt(col)) {
lcsLen = 1 + storage[kth][row + 1][col + 1];
 } else {
intfactor1 = storage[kth][row][col + 1];
intfactor2 = storage[kth][row + 1][col];

intfactor3 = 0;
if (kth >= 1)
factor3 = 1 + storage[kth - 1][row + 1][col + 1];

lcsLen = Math.max(factor1, Math.max(factor2, factor3));
 }
storage[kth][row][col] = lcsLen;
 }
 }
 }
returnstorage[K][0][0];
 }
/*
 private static void display(int[][][] strg) {
 for (int i = 0; i < strg.length; i++) {
 for (int j = 0; j < strg[i].length; j++) {
 // System.out.println(Arrays.toString(strg[i][j]));
 for (int k = 0; k < strg[i][j].length; k++) {
 System.out.print(strg[i][j][k] + " ");
 }
 System.out.println();
 }
 System.out.println();
 }
 }*/
}